/**
 * @param {number[]} nums
 * @return {number}
 */

// var reversePairs = function (nums) {
//   let ret = 0;
//   function getResult(nums, l, r) {
//     if (l >= r) return;
//     let mid = (l + r) >> 1;
//     getResult(nums, l, mid);
//     getResult(nums, mid + 1, r);

//     // 横跨两边的数量 -- 超时
//     for (let i = l; i <= mid; i++) {
//       for (let j = mid + 1; j <= r; j++) {
//         if (nums[j] < nums[i]) ret++;
//       }
//     }
//   };
//   getResult(nums, 0, nums.length - 1);
//   return ret;
// };

var reversePairs = function (nums) {
  let ret = 0;
  function getResult(nums, l, r) {
    if (l >= r) return;
    let mid = (l + r) >> 1;
    getResult(nums, l, mid);
    getResult(nums, mid + 1, r);


    let x = l, y = mid + 1, k = 0, temp = [];
    while (x <= mid || y <= r) {
      if ((y > r) || (x <= mid && nums[x] <= nums[y])) {
        temp[k++] = nums[x++];
      } else { // 左侧是值大于右侧的值
        temp[k++] = nums[y++];
        ret += mid - x + 1;
      };
    }
    for (let i = l; i <= r; i++) {
      nums[i] = temp[i - l];
    }
  };
  getResult(nums, 0, nums.length - 1);
  return ret;
};

let ret = reversePairs([7, 5, 6, 4]);
console.log(ret);